package com.nl.trees;

public class VerifySeqOfBST {

	
	/**
	 * 二叉搜索数，根节点大于左孩子，小于右孩子
	 * @param seq
	 * @param length
	 * @return
	 */
	public static boolean verfiySeqOfBST(int[] seq,int length){
		if(seq==null||length==0){
			return false;
		}
		
		int root = seq[length-1];
		
		//找到左右孩子的分界点
		int i=0;
		for(;i<length-1;i++){
			if(seq[i]>root){
				break;
			}
		}
		
		//判断右孩子是否满足条件
		int j=i;
		for(;j<length-1;j++){
			if(seq[j]<=root){
				return false;
			}
		}
		
		//验证左子树
		boolean left=true;
		if(i>0){
			left = verfiySeqOfBST(seq, i);
		}
		//验证右子树
		boolean right=true;
		if(i<length-1){
			int[] arr = new int[length-i-1];
			System.arraycopy(seq, 0, arr, 0, length-i-1);
			right=verfiySeqOfBST(arr,length-i-1 );
		}

		return left &&right;
	}
	public static void main(String[] args) {
		System.out.println(verfiySeqOfBST(new int[]{2,3,8,6,5}, 5));
	}
}
